[JS/백준]{이진 탐색}(1756) 피자 굽기

문제 설명

이 문제는 이진 탐색 문제이다 보통 이진 탐색 문제는 정렬된 배열이 필요한데 여기서는 정렬된

배열이 없다 그렇다면 정렬된 배열을 어떻게 얻을 수가 있을까?

5 6 4 3 6 2 3 맨 아래에는 3만큼의 넓이를 가진 오븐이 있다고 한다면 맨 아래에 도착하기 위해서는

2만큼의 넓이를 가진 도우만이 맨 아래에 들어갈 수가 있다. 그 이유는 맨 아래 바로 위의 넓이가 2이기

때문에 2 넓이의 통로를 지나기 위해서는 도우의 넓이가 2가 되어야 하기 때문이다.

사진을 보면 결국에는 5 5 4 3 3 2 2라는 정렬된 배열을 얻을 수가 있다.

그렇다면 만약에 3 넓이의 도우가 4번쨰 인덱스에 걸리기 위해서 로직을 짜준다.

만약 도우가 걸리지 않았다면 -1을 리턴하고 걸렸다면 걸린 이후 부분은 계산하지 않기 위해서

걸린 부분을 리턴한다. 여기서 처음에는 slice를 이용해서 걸리지 않은 부분을 잘라서 사용했지만

메모리 초과가 떠서 걸린 부분까지만 계산하도록 로직을 변경했다.

이런 식으로 모든 도우를 처리하면 된다.

코드

function binarySearch(list, target, left, right) {
  let mid = 0;
  let stopIdx = 0;
  let flag = false;

  while (left <= right) {
    mid = Math.floor((left + right) / 2);

    if (list[mid] >= target) {
      left = mid + 1;
      stopIdx = mid;
      flag = true;
    } else {
      right = mid - 1;
    }
  }
  if (flag) {
    return stopIdx + 1;
  }

  return -1;
}

let input = require("fs")
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [d, n] = input[0].split(" ").map(Number);
const ovenArr = input[1].split(" ").map(Number);
const doughArr = input[2].split(" ").map(Number);

let canOvenArr = [];

let curWidth = -1;

for (let i = 0; i < d; i++) {
  if (curWidth === -1) {
    curWidth = ovenArr[i];
    canOvenArr.push(curWidth);
  } else if (curWidth <= ovenArr[i]) {
    canOvenArr.push(curWidth);
  } else {
    curWidth = ovenArr[i];
    canOvenArr.push(curWidth);
  }
}

let hangOvenIdx = -2;

doughArr.forEach((val) => {
  if (hangOvenIdx === -2) {
    hangOvenIdx = binarySearch(canOvenArr, val, 0, canOvenArr.length - 1);
  } else {
    hangOvenIdx = binarySearch(canOvenArr, val, 0, hangOvenIdx - 2);
  }
});

if (hangOvenIdx === -1) {
  console.log(0);
} else {
  console.log(hangOvenIdx);
}